class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		vector<int> record;
		vector<vector<int> > result;

		sort(num.begin(), num.end());
		CalculateSum(num, target, 0, 0, record, result);
		return result;


    }

	void CalculateSum(const vector<int> &num, int target, int start, int sum, vector<int> &record, vector<vector<int> >& result) {
		for (int i = start; i < num.size(); ) {
			if (num[i] + sum > target) {
				break;
			}
			record.push_back(num[i]);
			if (num[i] + sum == target) {
				result.push_back(record);
			}
			CalculateSum(num, target, i + 1, sum + num[i], record, result);
			record.pop_back();
			++i;
			while (i < num.size() && num[i] == num[i - 1]) {
				++i;
			}
		}
	}

};